package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.TreeNode;

/**
 * @author jinhu
 * created 2021-05-15 15:32
 */
public class Solution_0108 {
    /**
     * 将有序数组转变为高度平衡二叉搜索树
     * 搜索二叉树，左子树都比根小，右子树都比根大
     * 左根右 ，中序遍历
     * <p>
     * 对于一个有序数组，创建一个二叉搜索树是无法确定一个固定的搜索二叉树
     * 加上限定条件也是无法确定一个唯一的搜索高度平衡的搜索二叉树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return this.buildTree(nums, 0, nums.length - 1);
    }

    public TreeNode buildTree(int nums[], int left, int right) {
        if (right < left) {
            return null;
        }
        int mid = (right + left) >> 1;   //有溢出风险
        TreeNode root = new TreeNode(nums[mid]);
        root.left = buildTree(nums, left, mid - 1);
        root.right = buildTree(nums, mid + 1, right);
        return root;
    }
}
